`
https://leetcode.cn/problems/snapshot-array/
`

// 题同 LC 981

/**
 * @param {number} length
 */
var SnapshotArray = function (length) {
  // 使用哈希表存储修改
  // 修改位置 -> [[快照ID, 修改值], [...], ...]
  // 这样快照ID便会严格递增，使用二分快速查找即可
  this.history = new Map()
  this.curSnapId = 0
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
SnapshotArray.prototype.set = function (index, val) {
  // 获取对应位置的存储数组
  if (!this.history.has(index)) {
    this.history.set(index, [])
  }
  const target = this.history.get(index)
  // 最后位置存的不是当前 id ，放个新的进去
  if (target.length === 0 || target.at(-1)[0] !== this.curSnapId) {
    target.push([this.curSnapId, val])
    return
  }
  // 最后位置存的是当前 id，直接修改即可
  target.at(-1)[1] = val
};

/**
 * @return {number}
 */
SnapshotArray.prototype.snap = function () {
  return this.curSnapId++
};

/** 
 * @param {number} index 
 * @param {number} snap_id
 * @return {number}
 */
SnapshotArray.prototype.get = function (index, snap_id) {
  const target = this.history.get(index) || []
  // 还没有修改记录，直接返回初始值
  if (target.length === 0) return 0
  // 找到最后一个 <= snap_id 的记录
  const recordIdx = _.sortedIndexBy(target, [snap_id + 1], ([snapId]) => snapId) - 1
  // 在 snap_id 之前没有修改记录，返回初始值
  if (recordIdx === -1) return 0
  // 找到 snap_id 最后的修改记录，返回对应的值
  return target[recordIdx][1]
};

/** 
 * Your SnapshotArray object will be instantiated and called as such:
 * var obj = new SnapshotArray(length)
 * obj.set(index,val)
 * var param_2 = obj.snap()
 * var param_3 = obj.get(index,snap_id)
 */